This invention relates to methods and apparatus for detecting the presence of a target in a scene that is described by an n-dimensional array of digital data samples.
Such an array can have X and Y dimensions which are perpendicular to each other, and the data sample at each X, Y location can give the intensity of light at that location. As another example, the array can have three dimensions X, Y, and Z which are perpendicular to each other; and the data sample at each X, Y, Z location can give the intensity of an x-ray at that location. As still another example, the array can have just a single dimension X; and each data sample along that dimension can give the magnitude of a voltage signal which comes from a microphone and represents speech or other sounds.
In each of the above arrays, a target that is to be recognized can be of any type. For example, in the above two-dimensional case, the target can be an airplane or a car; in the above three-dimensional case, the target can be a fracture in a bone; in the above one-dimensional case, the target can be certain words.
In the prior art, target recognition has been performed by comparing a data sample template of the target to all possible areas in the sampled data scene in which that template could occur. However, a major drawback of such a method is that it requires an extremely large number of comparisons to be performed; and that, in turn, limits the speed at which the targets can be recognized.
For example, consider the case of a two-dimensional scene which is described by a sampled data array that is 512.times.512 samples in size. Such a data array would make up a single frame of a television picture. Further assume that the target which is to be recognized fits into an area that is 20.times.20 data samples in size. To compare a 20.times.20 template of the target with just a single 20.times.20 portion of the sampled data scene would require a total of 400 comparisons. But in the entire 512.times.512 sampled data scene, the total number of 20.times.20 scene portions that exist is [512-20+1][512-20+1]or 243,049; and, each such scene portion needs to be compared on the target template. Thus, the total number of comparisons that need to be performed is (400)(243,049) or 97,219,600.
In addition, even after all of the above comparisons are made, a determination still cannot be made as to whether or not the target occurs in the scene. This is because, in any practical case, each target has a large number of variations. For example, the light intensity on parts of the target relative to the background can be increased or decreased. Also, the angular orientation of the target relative to the background can be rotated anywhere within 360.degree.. To account for all of these variations, many templates would have to be provided for each target; and, the above 97,219,600 comparisons would have to be performed using each template.
Accordingly, a primary object of the invention is to provide an improved method of recognizing targets which can be performed substantially faster than the above-described prior art method.
Another object of the invention is to provide an apparatus for carrying out the steps of the improved target recognition process.